{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Implement Rand10() Using Rand7()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #rejection-sampling #probability-and-statistics #randomized"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #拒绝采样 #概率与统计 #随机化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rand10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用 Rand7() 实现 Rand10()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定方法&nbsp;<code>rand7</code>&nbsp;可生成 <code>[1,7]</code> 范围内的均匀随机整数，试写一个方法&nbsp;<code>rand10</code>&nbsp;生成 <code>[1,10]</code> 范围内的均匀随机整数。</p>\n",
    "\n",
    "<p>你只能调用&nbsp;<code>rand7()</code>&nbsp;且不能调用其他方法。请不要使用系统的&nbsp;<code>Math.random()</code>&nbsp;方法。</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p>每个测试用例将有一个内部参数 <code>n</code>，即你实现的函数 <code>rand10()</code> 在测试时将被调用的次数。请注意，这不是传递给 <code>rand10()</code> 的参数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>1\n",
    "<strong>输出: </strong>[2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>2\n",
    "<strong>输出: </strong>[2,8]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>3\n",
    "<strong>输出: </strong>[3,8,10]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rand7()</code>调用次数的&nbsp;<a href=\"https://en.wikipedia.org/wiki/Expected_value\" target=\"_blank\">期望值</a>&nbsp;是多少&nbsp;?</li>\n",
    "\t<li>你能否尽量少调用 <code>rand7()</code> ?</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [implement-rand10-using-rand7](https://leetcode.cn/problems/implement-rand10-using-rand7/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [implement-rand10-using-rand7](https://leetcode.cn/problems/implement-rand10-using-rand7/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums = []\n",
    "        for _ in range(10):\n",
    "            nums.append(rand7())\n",
    "\n",
    "        import math\n",
    "        return sum(nums)%10+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    mem_map = {}\n",
    "    idx = 0\n",
    "    for i in range(1, 8):\n",
    "        for j in range(1, 8):\n",
    "            if idx >= 40:\n",
    "                break\n",
    "            mem_map[(i, j)] = idx % 10 + 1\n",
    "            idx += 1\n",
    "\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            l, r = rand7(), rand7()\n",
    "            print(l, r)\n",
    "            if (l, r) in self.mem_map:\n",
    "                return self.mem_map[(l, r)]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "def rand01():\n",
    "    res = rand7()\n",
    "    while res == 7:\n",
    "        res = rand7()\n",
    "    if res >= 4:\n",
    "        return 1\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        one = rand01()\n",
    "        two = rand01()\n",
    "        three = rand01()\n",
    "        four = rand01()\n",
    "        print(four , one, two, three)\n",
    "        res = (four << 3) + (one << 2) + (two << 1) + three \n",
    "        print(res)\n",
    "        while res < 1 or res > 10:\n",
    "            one = rand01()\n",
    "            two = rand01()\n",
    "            three = rand01()\n",
    "            four = rand01()\n",
    "            print(four , one, two, three)\n",
    "            res = (four << 3) + (one << 2) + (two << 1) + three \n",
    "            print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = 7*(rand7()-1)+rand7()\n",
    "        while n>40:\n",
    "            n = 7*(rand7()-1)+rand7()\n",
    "        return math.ceil(n/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = 7*(rand7()-1)+rand7()\n",
    "        while n>40:\n",
    "            n = 7*(rand7()-1)+rand7()\n",
    "        return math.ceil(n/4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        idx = 41\n",
    "        while idx > 40:\n",
    "            i, j = rand7(), rand7()\n",
    "            idx = (j - 1) * 7 + i\n",
    "        if idx % 10 == 0:\n",
    "            return 10\n",
    "        return idx % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        first = rand7()\n",
    "        second = rand7()\n",
    "        while first > 6:\n",
    "            first = rand7()\n",
    "        while second > 5:\n",
    "            second = rand7()\n",
    "\n",
    "        return second if first&1 else second + 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        total = 0\n",
    "        for i in range(10):\n",
    "            total += rand7()\n",
    "        return total%10 if total%10 != 0 else 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num = (rand7() - 1) * 7 + rand7()  # 生成 [1,49] 范围内的均匀随机数\n",
    "            if num <= 10:\n",
    "                return num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = (rand7()-1) * 7 + rand7()\n",
    "\n",
    "        while res > 40:\n",
    "            res = (rand7()-1) * 7 + rand7()\n",
    "        \n",
    "        return res % 10 + 1 \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            idx = (rand7() - 1) * 7 + rand7()\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            res = rand7() * 7 + rand7() - 8\n",
    "            if res < 40:\n",
    "                return res % 10 + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        while True:    \n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "\n",
    "            # 注意rand7是得到1-7的数字，要形成1-49的数字，需要a - 1\n",
    "            c = (a  - 1)* 7 + b\n",
    "\n",
    "            if c <= 40:\n",
    "                # 使得前4个数都是1，那么需要c - 1变成0-3\n",
    "                #return (c- 1)//4 + 1\n",
    "                return (c - 1) % 10 + 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num=(rand7()-1)*7+rand7()\n",
    "            if num<=40:\n",
    "                return (num-1)%10+1\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #a =  #1-49\n",
    "        a = (rand7()-1)*7 + rand7()\n",
    "        while a>40:\n",
    "            a = (rand7()-1)*7 + rand7()   \n",
    "        return 1+(a-1)%10 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        r1 = r2 = True\n",
    "        s1 = s2 = 0\n",
    "        while r1:\n",
    "            s1 = rand7()\n",
    "            if s1 <= 5:\n",
    "                r1 = False\n",
    "        while r2:\n",
    "            s2 = rand7()\n",
    "            if s2 <= 2:\n",
    "                r2 = False\n",
    "                if s2 == 1:\n",
    "                    s2 = 0\n",
    "                elif s2 == 2:\n",
    "                    s2 = 5\n",
    "        return s1 + s2\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "            idx = (a - 1) * 7 + b\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "            a = idx - 40\n",
    "            b = rand7()\n",
    "            # get uniform dist from 1 - 63\n",
    "            idx = (a - 1) * 7 + b\n",
    "            if idx <= 60:\n",
    "                return 1 + (idx - 1) % 10\n",
    "            a = idx - 60\n",
    "            b = rand7()\n",
    "            # get uniform dist from 1 - 21\n",
    "            idx = (a - 1) * 7 + b\n",
    "            if idx <= 20:\n",
    "                return 1 + (idx - 1) % 10\n",
    "\n",
    "# 里面有说求期望的方法\n",
    "# 链接：https://leetcode.cn/problems/implement-rand10-using-rand7/solutions/978527/yong-rand7-shi-xian-rand10-by-leetcode-s-qbmd/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = 11\n",
    "        while x > 10:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            x = (row - 1) * 7 + col\n",
    "        \n",
    "        return x\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 10ci\n",
    "        while True:\n",
    "            # print(1)\n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "            if b == 1:\n",
    "                return a\n",
    "            elif b == 2:\n",
    "                if a < 4:\n",
    "                    return 7 + a\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 加0,1,2,3\n",
    "        num = (rand7()-1)*7+rand7()\n",
    "        while num > 40:\n",
    "            num =  (rand7()-1)*7+rand7()\n",
    "        \n",
    "        return num % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 加0,1,2,3\n",
    "        while True:\n",
    "            num = (rand7()-1)*7+rand7()\n",
    "            if num <= 40 :\n",
    "                return num % 10 + 1          \n",
    "            num = (num - 40 - 1)*7+rand7()\n",
    "            if num <= 60 :\n",
    "                return num % 10 + 1\n",
    "            num = (num -60 - 1)*7+rand7()\n",
    "            if num <= 20 :\n",
    "                return num %10 +1\n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row-1)*7+col\n",
    "            if idx<=40:\n",
    "                return 1+(idx-1)%10\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            row=rand7()\n",
    "            col=rand7()\n",
    "            idx=(row-1)*7+col\n",
    "            if idx<=40:\n",
    "                return (idx-1)%10+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        while not 1 <= res <= 10:\n",
    "            res = (rand7() - 1) * 7 + rand7()\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return randint(1, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            index = (rand7()-1) * 7 + rand7()\n",
    "            if index <= 40:\n",
    "                return (index-1) % 10 + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x1, x2 = rand7()-1, rand7()-1\n",
    "        while 7*x1+x2 >= 40:\n",
    "            x1, x2 = rand7()-1, rand7()-1\n",
    "        \n",
    "        return (7*x1+x2)%10 +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            x = rand7()\n",
    "            y = rand7()\n",
    "            s = (x-1)*7 + y\n",
    "            if s <= 40:\n",
    "                return 1 + s % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        num = (rand7() - 1) * 7 + rand7() # 取得0-48之间的数字\n",
    "        # 如数字>39 （40-48），舍弃，重新选取\n",
    "        while num > 40:\n",
    "            num =  (rand7() - 1) * 7 + rand7()  \n",
    "        # 如数字在0-39之间，模10加一，恰好可以等概率取得1-10之间的十个数字\n",
    "        return num % 10 + 1    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = (rand7() - 1) * 7 + rand7() - 1\n",
    "        return self.rand10() if x >= 40 else x % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "# class Solution:\n",
    "#     def rand10(self):\n",
    "#         \"\"\"\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "            \n",
    "            \n",
    "# class Solution:\n",
    "#     def rand10(self) -> int:\n",
    "#         while True:\n",
    "#             a = rand7()\n",
    "#             b = rand7()\n",
    "#             idx = (a - 1) * 7 + b\n",
    "#             if idx <= 40:\n",
    "#                 return 1 + (idx - 1) % 10\n",
    "#             a = idx - 40\n",
    "#             b = rand7()\n",
    "#             # get uniform dist from 1 - 63\n",
    "#             idx = (a - 1) * 7 + b\n",
    "#             if idx <= 60:\n",
    "#                 return 1 + (idx - 1) % 10\n",
    "#             a = idx - 60\n",
    "#             b = rand7()\n",
    "#             # get uniform dist from 1 - 21\n",
    "#             idx = (a - 1) * 7 + b\n",
    "#             if idx <= 20:\n",
    "#                 return 1 + (idx - 1) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            r, c = rand7(), rand7()\n",
    "            idx = (r - 1) * 7 + c\n",
    "            if idx <= 40:\n",
    "                return (idx - 1) % 10 + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        '''\n",
    "        先生成一个7*7的矩阵，拒绝多余的9个\n",
    "        '''\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            index = (row - 1) * 7 + col\n",
    "            if index <= 40:\n",
    "                return (index-1) % 10 + 1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        tab = {2 : 1,3 : 2,5 : 3,7 : 4,8 : 5,10 : 6,14 : 7,15 : 8,20 : 9,21 : 10}\n",
    "        n = 0\n",
    "        while n not in tab:\n",
    "            n = rand7() * rand7()\n",
    "        return tab[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            # 1)生成rand49()\n",
    "            index=(rand7()-1)*7+rand7()\n",
    "            if (index<=10):\n",
    "                return index\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            a = rand7()\n",
    "            b = rand7()\n",
    "            n = (a - 1) * 7 + b\n",
    "            if n <= 40: return n % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x1, x2 = rand7()-1, rand7()\n",
    "        while 7*x1+x2 > 40:\n",
    "            x1, x2 = rand7()-1, rand7()\n",
    "        \n",
    "        return (7*x1+x2)%10 +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ret=11\n",
    "        while ret>10:\n",
    "            ret=1\n",
    "            for i in range(4):\n",
    "                temp=rand7()\n",
    "                while temp==4:temp=rand7()\n",
    "                if temp>4:ret+=2**i\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            r0 = rand7()\n",
    "            r1 = rand7()\n",
    "            v = r0 + (r1 - 1) * 7\n",
    "            if v > 40:\n",
    "                r0 = v % 40  # 1-9\n",
    "                r1 = rand7() # 1-7\n",
    "                v = r0 + (r1 - 1) * 7 # 1-63\n",
    "                if v > 60:\n",
    "                    r0 = v % 60 # 1 2 3\n",
    "                    r1 = rand7() # 1-7\n",
    "                    v = r0 + (r1 - 1) * 7 # 21\n",
    "                    if v > 20:\n",
    "                        continue\n",
    "                    else:\n",
    "                        return 1 + (v - 1) % 10\n",
    "                else:\n",
    "                    return 1 + (v - 1) % 10\n",
    "            return 1 + (v - 1) % 10\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x = 11\n",
    "        while x > 10:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            x = (row - 1) * 7 + col\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num = rand7() + (rand7() - 1) * 7\n",
    "            if num <= 40:\n",
    "                return 1 + (num - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "class Solution:\n",
    "    def rand10(self) -> int:\n",
    "        while True:\n",
    "            row = rand7()\n",
    "            col = rand7()\n",
    "            idx = (row - 1) * 7 + col\n",
    "            if idx <= 40:\n",
    "                return 1 + (idx - 1) % 10\n",
    "\n",
    "\n",
    "# 1/7\n",
    "# 选两次, 就有如下结果:\n",
    "\n",
    "# 1 2 3 4 5 6 7\n",
    "# 1 2 3 4 5 6 7\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a,b = 0, 0\n",
    "        while True:\n",
    "            a=rand7()\n",
    "            if a<7:\n",
    "                break \n",
    "        while True:\n",
    "            b=rand7()\n",
    "            if b<6:\n",
    "                break   \n",
    "        return b if a%2==0 else b+5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            num = (rand7() - 1) * 7 + rand7()\n",
    "            if not 1 <= num <= 10:\n",
    "                continue\n",
    "            return num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        while True:\n",
    "            #r = (rand7() - 1) * 7 + rand7()\n",
    "            #if r <= 40: return r % 10 + 1\n",
    "            r = rand7() * 7 - rand7()\n",
    "            if r < 40: return r % 10 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# The rand7() API is already defined for you.\n",
    "# def rand7():\n",
    "# @return a random integer in the range 1 to 7\n",
    "\n",
    "class Solution:\n",
    "    def rand10(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num1=rand7()\n",
    "        num2=rand7()\n",
    "        num=num1*10+num2\n",
    "        #依据num生成答案\n",
    "        #num是一个8进制数，它的第0，1位是【1，7】中的随机数\n",
    "        #转换为十进制数四十九种可能，我们取其中10种\n",
    "        while num>=66:\n",
    "            num1=rand7()\n",
    "            num2=rand7()\n",
    "            num=num1*10+num2\n",
    "        \n",
    "        if num<=14:return 1\n",
    "        elif num<=21:return 2\n",
    "        elif num<=25:return 3\n",
    "        elif num<=32:return 4\n",
    "        elif num<=36:return 5\n",
    "        elif num<=43:return 6\n",
    "        elif num<=47:return 7\n",
    "        elif num<=54:return 8\n",
    "        elif num<=61:return 9\n",
    "        elif num<=65:return 10\n",
    "        return 1\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
